The memory hierarchy forms the basic underpinnings of computer systems. As different memory technologies improve in performance at different rates, managing this hierarchy effectively is increasingly the key to achieving good system performance and cost/performance. The techniques for managing the memory hierarchy are generally referred to as caching techniques. Thus far, the emphasis in caching has been on reducing the miss ratio, i.e., the fraction of requests that cannot be satisfied by the cache. But misses vary in their penalty or cost. For example, a request that has to go to a remote site will cost a lot more than one that can be satisfied locally. Also, a request that hits in a downstream cache will cost orders of magnitude less than one requiring a mechanical movement in some storage device. A caching system that makes no distinction between these different requests is dramatically under utilizing the cache space.
There has been some work on cache replacement algorithms that try to include replacement cost in the replacement decision. But such algorithms have a very high processing overhead because they have to maintain some ordering of the blocks based on their replacement cost. An attempt to overcome this problem has been proposed. The proposal provides for the partitioning of the cache so that there is one partition per device, and to adjust the partition sizes to balance the work across the devices. This, however, requires the user or administrator to know the device boundaries and to set up the caching system accordingly. Such information may change and is not easily available when virtualization is used. In addition, it requires many more partitions than necessary, incurring additional overhead and inefficiencies. Moreover, it is focused only on reducing skew across devices and does not handle cost differences that are disclosed by the user/application or that might arise from the type of data (e.g., metadata, log), type of operation (e.g., write, sequential), location of the data etc.
There remains therefore a great need for a caching system that takes into account the different replacement costs of the blocks and yet has low overhead. The present invention satisfies this need by dynamically partitioning the cache based on the replacement cost of blocks.